import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-28
 * Time: 11:35
 */

public class Solution {
    /**
     *  方法一: 窗口中的数字全部在数组中存好
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (sum <= 0) {
            return ans;
        }
        int left = 1;
        int s = 1;
        Deque<Integer> deque = new LinkedList<>();
        deque.add(1);
        for (int i = 2; i < sum; i++) {
            s += i;
            deque.add(i);
            if (s == sum) {
                ans.add(new ArrayList<>(deque));
            }
            while (s > sum && left < i) {
                s -= left;
                left++;
                deque.removeFirst();
                if (s == sum){
                    ans.add(new ArrayList<>(deque));
                }
            }
        }
        return ans;
    }


    /**
     *  方法二: 等到找到符合条件的序列再遍历窗口
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer> > FindContinuousSequence2(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (sum <= 0) {
            return ans;
        }
        int left = 1;
        int right = 2;
        while (left < right && right < sum){
            int s =  (right - left + 1) * (left + right) / 2;
            if (s == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = left;i <= right;i++){
                    list.add(i);
                }
                ans.add(list);
                right++;
            }else if (s > sum){
                left++;
            }else{
                right++;
            }
        }
        return ans;
    }
}
